1660D - Maximum Product Strikes Back - CodeForces Solution

#include <bits/stdc++.h>

#define IN cin
#define OUT cout

using namespace std;

#define FOR(a,b,c) for(int a=b; a < c; a++)


int T;
int N;
vector<int> A;
vector<int> C2;

int FindNextNonZero(int pos)
{
	FOR(i,pos,N)
	{
		assert(i >= 0 && i < N);
		if(A[i] != 0)
			return i;
	}
	return -1;
}

int FindNextZero(int pos)
{
	FOR(i,pos,N)
	{
		assert(i >= 0 && i < N);		
		if(A[i] == 0)
			return i;
	}
	return -1;
}

pair<int, pair<int, int>> comp(int lower, int upper)
{
	if(lower == upper)
	{
		if(A[lower] == 2)
			return {1, {lower, N-1-lower}};
		else
			return {0,{-1,-1}};
	}
	
	assert(lower >= 0 && upper < N && lower <= upper);
	int neg_count = 0;
	int first_neg = -1;
	int last_neg = -1;
	for(int i = lower; i <= upper; i++)
	{
		assert(i >= 0 && i < N);
		if(A[i] < 0)
		{
			neg_count++;
			last_neg = i;
		}
	}
	for(int i=lower; i <= upper; i++)
	{
		assert(i >= 0 && i < N);
		if(A[i] < 0)
		{
			first_neg = i;
			break;
		}
	}
	if(neg_count % 2 == 0)
	{
		int prod;
		if(lower > 0)
			prod = C2[upper] - C2[lower-1];
		else
			prod = C2[upper];
		
		return {prod, {lower, N-upper-1}};
	}
	

	
	int left_prod = 0;
	if(lower > 0 && last_neg > 0)
		left_prod = C2[last_neg-1] - C2[lower -1];
	else if(last_neg > 0)
		left_prod = C2[last_neg-1];
	
	
	int right_prod = C2[upper] - C2[first_neg];
	
	
	if(right_prod > left_prod)
	{
	
		return {right_prod,{first_neg + 1, N-upper-1}};
	}
	
	return {left_prod,{lower, N-last_neg}};
}


pair<int, int> solve()
{
	A = vector<int>(N);
	C2 = vector<int>(N);
	FOR(n,0,N)
	{
		IN >> A[n];
		if(n == 0)
		{
			C2[0] = (A[n] == -2 || A[n] == 2);
		} else
		{
			C2[n] = C2[n-1] + (A[n] == -2 || A[n] == 2);
		}
	}
	
	int first_nonzero = FindNextNonZero(0);
	if(first_nonzero == -1)
		return {N, 0};
	
	int index = first_nonzero;
	vector<pair<int, int>> Q;
	while(index < N)
	{
		int next_zero = FindNextZero(index);
		if(next_zero == -1)
		{
			Q.push_back({index, N-1});
			break;
		} else
		{
			Q.push_back({index, next_zero -1});
		}
		index = FindNextNonZero(next_zero + 1);
		if(index == -1)
			break;
	}
	

	int prod = 0;
	pair<int, int> ans = {N,0};
	for(auto [l, u] : Q)
	{
		auto [a, p] = comp(l,u);
		if(a > prod)
		{
			ans = p;
			prod = a;
		}
		
	}
	
	return ans;
}


int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ////////////////////////
    ////////////////////////
	
	IN >> T;
	FOR(t,0,T)
	{
		IN >> N;
		auto [x,y] = solve();
		OUT << x << " " << y << "\n";
	
	}
	OUT << flush;
}